import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/12 14:53
 * @description TreeMap
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int[] maximumBeauty(int[][] items, int[] queries) {
        // 按价格升序排序
        Arrays.sort(items, (a, b) -> {
            return a[0] - b[0];
        });
        // 预处理最大的美丽值
        int n = items.length;
        for (int i = 1; i < n; i++) {
            items[i][1] = Math.max(items[i][1], items[i-1][1]);
        }
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            // 二分查找 <= 该价格的物品
            int idx = check(items, queries[i]);
            if (idx != -1) {
                ans[i] = items[idx][1];
            }
        }
        return ans;
    }
    public int check(int[][] items, int q) {
        int l = -1, r = items.length;
        while (l + 1 != r) {
            int mid = (l + r) / 2;
            if (items[mid][0] > q) {
                r = mid;
            }else {
                l = mid;
            }
        }
        return l;
    }
}
